home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / lfsrebuild / layout.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-12  |  13.5 KB  |  499 lines
  1.  
  2.  
  3. #ifdef __STDC__
  4. #define _HAS_PROTOTYPES
  5. #endif
  6.  
  7. #include <cfuncproto.h>
  8. #include <varargs.h>
  9. #include <sprite.h>
  10. #include <stdio.h>
  11. #include <sys/types.h>
  12. #include <option.h>
  13. #include <stdlib.h>
  14. #include <string.h>
  15. #include <sys/file.h>
  16. #include <alloca.h>
  17. #include <bstring.h>
  18. #include <unistd.h>
  19. #include <bit.h>
  20. #include <time.h>
  21. #include <sys/time.h>
  22. #include <fs.h>
  23. #include <kernel/fs.h>
  24. #include <kernel/dev.h>
  25. #include <kernel/fsdm.h>
  26. #include <kernel/fslcl.h>
  27. #include <kernel/devDiskLabel.h>
  28.  
  29. #include <kernel/lfsDesc.h>
  30. #include <kernel/lfsDescMap.h>
  31. #include <kernel/lfsFileLayout.h>
  32. #include <kernel/lfsDirOpLog.h>
  33. #include <kernel/lfsSegLayout.h>
  34. #include <kernel/lfsStableMem.h>
  35. #include <kernel/lfsSuperBlock.h>
  36. #include <kernel/lfsUsageArray.h>
  37. #include <kernel/lfsStats.h>
  38.  
  39. #include "layout.h"
  40. #include "fscheck.h"
  41.  
  42. #define    MIN_SUMMARY_REGION_SIZE    16
  43. /*
  44.  * Macro returning TRUE if segment is completely empty.
  45.  */
  46. #define SegIsEmpty(segPtr) (((segPtr)->numBlocks == 1) &&         \
  47.         ((segPtr)->curSegSummaryPtr->size == sizeof(LfsSegSummary)))
  48.  
  49. static void AddNewSummaryBlock _ARGS_((LfsSeg *segPtr));
  50. static Boolean WriteSegment _ARGS_((int diskId, LfsSeg *segPtr));
  51.  
  52. Boolean
  53. LayoutCheckpoint(segPtr, checkPointPtr, sizePtr)
  54.     LfsSeg    *segPtr;
  55.     char *checkPointPtr;
  56.     int *sizePtr;
  57. {
  58.     int    moduleType, startOffset;
  59.     Boolean full;
  60.     char    *summaryPtr, *endSummaryPtr;
  61.     int        newStartBlockOffset;
  62.     LfsCheckPointRegion    *segUsageCheckpointRegionPtr;
  63.  
  64.     full = FALSE;
  65.     segUsageCheckpointRegionPtr = (LfsCheckPointRegion *) NIL;
  66.     for(moduleType = 0; moduleType < LFS_MAX_NUM_MODS; moduleType++) {
  67.     /*
  68.      * Filling in a segment, be sure that there is enough
  69.      * room for the LfsSegSummaryHdr.
  70.      */
  71.     summaryPtr = LfsSegSlowGrowSummary(segPtr, 1,
  72.         sizeof(LfsSegSummaryHdr) + MIN_SUMMARY_REGION_SIZE, TRUE);
  73.     if (summaryPtr == (char *) NIL) {
  74.         full = TRUE;
  75.         break;
  76.     }
  77.     segPtr->curSummaryHdrPtr = (LfsSegSummaryHdr *)  summaryPtr;
  78.     LfsSegSetSummaryPtr(segPtr, summaryPtr + sizeof(LfsSegSummaryHdr));
  79.     startOffset = segPtr->curBlockOffset;
  80.     {
  81.         int    size;
  82.         LfsCheckPointRegion    *regionPtr;
  83.         regionPtr = (LfsCheckPointRegion *) checkPointPtr;
  84.         size = 0;
  85.         if (moduleType == LFS_SEG_USAGE_MOD) {
  86.         full = LfsSegUsageCheckpoint(segPtr, (char *)(regionPtr + 1),
  87.                      &size);
  88.         } else if (moduleType == LFS_DESC_MAP_MOD) {
  89.         full = LfsDescMapCheckpoint(segPtr, (char *)(regionPtr + 1),
  90.                      &size);
  91.         } else {
  92.         full = FALSE;
  93.         }
  94.         if (full) {    
  95.         break;
  96.         }
  97.         if (size > 0) {
  98.         if (moduleType == LFS_SEG_USAGE_MOD) {
  99.             segUsageCheckpointRegionPtr = regionPtr;
  100.         }
  101.         regionPtr->type = moduleType;
  102.         regionPtr->size = size + sizeof(LfsCheckPointRegion);
  103.         *sizePtr += regionPtr->size;
  104.         checkPointPtr += regionPtr->size;
  105.         }
  106.     }
  107.      /*
  108.       * If the callback added data to the segment, fill in the summary 
  109.       * header. 
  110.       */
  111.      endSummaryPtr = LfsSegGetSummaryPtr(segPtr); 
  112.      if ((startOffset != segPtr->curBlockOffset) ||
  113.          ((summaryPtr + sizeof(LfsSegSummaryHdr)) != endSummaryPtr)) {
  114.         segPtr->curSummaryHdrPtr->moduleType = moduleType;
  115.         segPtr->curSummaryHdrPtr->lengthInBytes = endSummaryPtr - 
  116.                 (char *) summaryPtr;
  117.         segPtr->curSummaryHdrPtr->numDataBlocks =  
  118.                 segPtr->curBlockOffset - startOffset;
  119.      } else {
  120.          LfsSegSetSummaryPtr(segPtr, summaryPtr);
  121.      }
  122.     if (full) {    
  123.         if (LfsSegSummaryBytesLeft(segPtr) > MIN_SUMMARY_REGION_SIZE) {
  124.         break;
  125.         }
  126.     }
  127.   }
  128.    /*
  129.     * Update the size of the last summary block and cap off this segment. 
  130.     */
  131.    segPtr->curSegSummaryPtr->size = segPtr->curSummaryPtr - 
  132.                     (char *) segPtr->curSegSummaryPtr;
  133.  
  134.    newStartBlockOffset = -1;
  135.    if (!full) {
  136.     if (SegIsEmpty(segPtr)) { 
  137.         /*
  138.          * The segment is totally empty.  We don't need to write
  139.          * this one yet.
  140.          */
  141.         newStartBlockOffset = segPtr->startBlockOffset;
  142.     } else if ((segPtr->curDataBlockLimit -  segPtr->curBlockOffset) > 
  143.                10) { 
  144.         /*
  145.          * If this is considered to be a partial segment write add the
  146.          * summary block we needed.
  147.          */
  148.         AddNewSummaryBlock(segPtr);
  149.         newStartBlockOffset = segPtr->curBlockOffset-1;
  150.     }
  151.    }
  152.    LfsSetLogTail(&segPtr->logRange, newStartBlockOffset, 
  153.                     segPtr->activeBytes);  
  154.    if (segUsageCheckpointRegionPtr != (LfsCheckPointRegion *) NIL) {
  155.        LfsSegUsageCheckpointUpdate( 
  156.             (char *) (segUsageCheckpointRegionPtr + 1),
  157.             segUsageCheckpointRegionPtr->size - 
  158.                     sizeof(*segUsageCheckpointRegionPtr));
  159.     }
  160.  
  161.     return full;
  162. }
  163.  
  164.  
  165. /*
  166.  *----------------------------------------------------------------------
  167.  *
  168.  * LfsSegSlowGrowSummary --
  169.  *
  170.  *    Insure that there is enought room for an object with the 
  171.  *    specified number of blocks and summary bytes. Possibly add a
  172.  *    new summary block if needed.
  173.  *
  174.  * Results:
  175.  *    A pointer to the summary bytes for this region or NIL if
  176.  *    there is not enought room.
  177.  *
  178.  * Side effects:
  179.  *
  180.  *----------------------------------------------------------------------
  181.  */
  182.  
  183. char *
  184. LfsSegSlowGrowSummary(segPtr, dataBlocksNeeded, sumBytesNeeded, addNewBlock)
  185.     register LfsSeg    *segPtr;    /* Segment of interest. */
  186.     int     dataBlocksNeeded;        /* Number of data blocks needed. */
  187.     int    sumBytesNeeded;            /* Number of summary bytes needed. */
  188.     Boolean addNewBlock;        /* Added a new block if necessary. */
  189. {
  190.     int     sumBytesLeft, blocksLeft, sumBlocks;
  191.  
  192.     /*
  193.      * Test the most common case first. Do the data and summary fit
  194.      * in the current configuration. 
  195.      */
  196.     sumBytesLeft = LfsSegSummaryBytesLeft(segPtr);
  197.     blocksLeft = LfsSegBlocksLeft(segPtr);
  198.     if ((blocksLeft >= dataBlocksNeeded) && (sumBytesLeft >= sumBytesNeeded)) {
  199.        return segPtr->curSummaryPtr;
  200.     }
  201.     /*
  202.      * Need to add a summary block. Bail if the user doesn't what it 
  203.      * or there is not enought room.
  204.      */
  205.     sumBlocks = 1;
  206.     if (!addNewBlock || (dataBlocksNeeded + sumBlocks > blocksLeft)) { 
  207.     return (char *) NIL;
  208.     }
  209.     /*
  210.      * Malloc a new summary buffer and add it to the segment.
  211.      */
  212.     AddNewSummaryBlock(segPtr);
  213.     return segPtr->curSummaryPtr;
  214. }
  215.  
  216. /*
  217.  *----------------------------------------------------------------------
  218.  *
  219.  * LfsSegSlowDiskAddress --
  220.  *
  221.  *    Compute the disk address of a LfsSegElement.
  222.  *
  223.  * Results:
  224.  *    The disk address of the element.
  225.  *
  226.  * Side effects:
  227.  *    None.
  228.  *
  229.  *----------------------------------------------------------------------
  230.  */
  231.  
  232. int
  233. LfsSegSlowDiskAddress(segPtr, segElementPtr)
  234.     register LfsSeg    *segPtr;     /* Segment of interest. */
  235.     LfsSegElement *segElementPtr; /* Segment element of interest. */
  236. {
  237.     int    elementNumber, blockOffset;
  238.     int    newDiskAddr;
  239.  
  240.     /*
  241.      * Check the common case that we are asking about the "current"
  242.      * element. 
  243.      */
  244.     elementNumber = segElementPtr - segPtr->segElementPtr;
  245.  
  246.     if (elementNumber == segPtr->curElement) {
  247.     blockOffset = segPtr->curBlockOffset;
  248.     } else {
  249.     int    i;
  250.     blockOffset = segPtr->startBlockOffset;
  251.     for (i = 0; i <= elementNumber; i++) {
  252.         blockOffset += segPtr->segElementPtr[i].lengthInBlocks;
  253.     }
  254.     }
  255.     newDiskAddr = segPtr->logRange.current * 
  256.             superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize + 
  257.           superBlockPtr->hdr.logStartOffset;
  258.     newDiskAddr += superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize - blockOffset;
  259.     return newDiskAddr;
  260. }
  261.  
  262. /*
  263.  *----------------------------------------------------------------------
  264.  *
  265.  * LfsSegSlowAddDataBuffer --
  266.  *
  267.  *    Add a LfsSegElement to a segment.
  268.  *
  269.  * Results:
  270.  *    A pointer to the LfsSegElement added. NIL if the object would not
  271.  *    fit.
  272.  *
  273.  * Side effects:
  274.  *    None.
  275.  *
  276.  *----------------------------------------------------------------------
  277.  */
  278.  
  279. LfsSegElement *
  280. LfsSegSlowAddDataBuffer(segPtr, blocks, bufferPtr, clientData)
  281.     register LfsSeg    *segPtr;  /* Segment to add to. */ 
  282.     int            blocks;      /* Size of buffer to add in blocks */
  283.     char   *bufferPtr;      /* Buffer to add. */
  284.     ClientData clientData; /* ClientData associated with this field. */
  285. {
  286.     LfsSegElement *elementPtr;
  287.  
  288.     if (segPtr->curBlockOffset + blocks > segPtr->curDataBlockLimit) {
  289.     return (LfsSegElement *) NIL;
  290.     }
  291.     segPtr->curElement++;
  292.     segPtr->curBlockOffset += blocks;
  293.  
  294.     elementPtr = segPtr->segElementPtr + segPtr->curElement;
  295.     elementPtr->lengthInBlocks = blocks;
  296.     elementPtr->clientData = clientData;
  297.     elementPtr->address    = bufferPtr;
  298.     segPtr->numElements = segPtr->curElement+1;
  299.     segPtr->numBlocks += blocks;
  300.     return elementPtr;
  301. }
  302.  
  303. /*
  304.  *----------------------------------------------------------------------
  305.  *
  306.  * AddNewSummaryBlock --
  307.  *
  308.  *  Add a summary block to a segment.
  309.  *
  310.  * Results:
  311.  *    None.
  312.  *
  313.  * Side effects:
  314.  *    A new summary block is malloc() and initialized.
  315.  *
  316.  *----------------------------------------------------------------------
  317.  */
  318. static void
  319. AddNewSummaryBlock(segPtr)
  320.     LfsSeg    *segPtr;    /* Seg to add block to. */
  321. {
  322.     LfsSegElement *sumBufferPtr;
  323.     LfsSegSummary *newSummaryPtr;
  324.     int          sumBytes;
  325.  
  326.     sumBytes = superBlockPtr->hdr.blockSize;
  327.     sumBufferPtr = LfsSegAddDataBuffer(segPtr, 1, malloc(sumBytes),
  328.                     (ClientData) NIL);
  329.     newSummaryPtr =  (LfsSegSummary *) sumBufferPtr->address;
  330.     newSummaryPtr->magic = LFS_SEG_SUMMARY_MAGIC;
  331.     newSummaryPtr->timestamp = ++currentTimestamp;
  332.     newSummaryPtr->prevSeg = segPtr->logRange.prevSeg;
  333.     newSummaryPtr->nextSeg = segPtr->logRange.nextSeg;
  334.     newSummaryPtr->size = sizeof(LfsSegSummary);
  335.     newSummaryPtr->nextSummaryBlock = -1;
  336.  
  337.     if (segPtr->curSegSummaryPtr != (LfsSegSummary *) NIL) { 
  338.     /*
  339.      * This is not the first summary block in the segment.  Fixup the
  340.      * size of the last summary block and point it at the new one. 
  341.      */
  342.     segPtr->curSegSummaryPtr->size = segPtr->curSummaryPtr - 
  343.                     (char *) (segPtr->curSegSummaryPtr);
  344.     segPtr->curSegSummaryPtr->nextSummaryBlock = segPtr->curBlockOffset;
  345.     } 
  346.     segPtr->curSegSummaryPtr = newSummaryPtr;
  347.  
  348.     segPtr->curSummaryPtr = sumBufferPtr->address + sizeof(LfsSegSummary);
  349.     segPtr->curSummaryLimitPtr = sumBufferPtr->address + sumBytes;
  350. }
  351.  
  352. void
  353. CopySegToBuffer( segPtr, maxSize, bufferPtr, lenPtr)
  354.     LfsSeg    *segPtr;
  355.     int        maxSize;
  356.     char    *bufferPtr;
  357.     int        *lenPtr;
  358. {
  359.     int bytes, offset;
  360.     LfsSegElement *elementPtr;
  361.  
  362.     *lenPtr = 0;
  363.     offset = 0;
  364.     while ((segPtr->curElement >= 0)) {
  365.     elementPtr = segPtr->segElementPtr + segPtr->curElement;
  366.     bytes = elementPtr->lengthInBlocks  * superBlockPtr->hdr.blockSize;
  367.      bcopy(elementPtr->address, bufferPtr + *lenPtr, bytes);
  368.     *lenPtr += bytes;
  369.     segPtr->curElement--;
  370.     }
  371. }
  372.  
  373.  
  374. /*
  375.  *----------------------------------------------------------------------
  376.  *
  377.  * DestorySegStruct --
  378.  *
  379.  *    Destory an LfsSeg structure.
  380.  *
  381.  * Results:
  382.  *    None.
  383.  *
  384.  * Side effects:
  385.  *    None.
  386.  *
  387.  *----------------------------------------------------------------------
  388.  */
  389.  
  390. static void
  391. DestorySegStruct(segPtr)
  392.     LfsSeg    *segPtr;    /* Segment to Destory. */
  393. {
  394.  
  395.  
  396.     free((char *) segPtr->segElementPtr);
  397.     free((char *)segPtr);
  398. }
  399.  
  400.  
  401. /*
  402.  *----------------------------------------------------------------------
  403.  *
  404.  * GetSegStruct --
  405.  *
  406.  *    Allocate an LfsSeg structure.
  407.  *
  408.  * Results:
  409.  *    A lfsSeg structure
  410.  *
  411.  * Side effects:
  412.  *    None.
  413.  *
  414.  *----------------------------------------------------------------------
  415.  */
  416.  
  417. static LfsSeg *
  418. GetSegStruct(segLogRangePtr, startBlockOffset)
  419.     LfsSegLogRange *segLogRangePtr; /* Log range of segment. */
  420.     int           startBlockOffset; /* Starting block offset into segment */
  421. {
  422.     LfsSeg    *segPtr;
  423.  
  424.     segPtr = (LfsSeg *) calloc(1, sizeof(LfsSeg));
  425.     segPtr->segElementPtr = 
  426.         (LfsSegElement *) malloc(sizeof(LfsSegElement) * 
  427.             superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize);
  428.     segPtr->logRange = *segLogRangePtr;
  429.     segPtr->numElements = 0;
  430.     segPtr->numBlocks = 0;
  431.     segPtr->startBlockOffset = startBlockOffset;
  432.     segPtr->activeBytes = 0;
  433.     segPtr->curSegSummaryPtr = (LfsSegSummary *) NIL;
  434.     segPtr->curSummaryHdrPtr = (LfsSegSummaryHdr *) NIL;
  435.     segPtr->curElement = -1;
  436.     segPtr->curBlockOffset = segPtr->startBlockOffset;
  437.     segPtr->curDataBlockLimit = superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize;
  438.     segPtr->curSummaryPtr = (char *) NIL;
  439.     segPtr->curSummaryLimitPtr = (char *) NIL;
  440.  
  441.     return segPtr;
  442. }
  443. Boolean
  444. WriteSegCheckpoint(diskId, checkPointPtr, checkPointSizePtr)
  445.     int    diskId;
  446.     char *checkPointPtr;
  447.     int    *checkPointSizePtr;
  448. {
  449.     LfsSeg    *segPtr;
  450.     LfsSegLogRange    segLogRange;
  451.     int        startBlock;
  452.     Boolean full;
  453.  
  454.     full = TRUE;
  455.     while (full) {
  456.     LfsGetLogTail( &segLogRange, &startBlock);
  457.     segPtr = GetSegStruct(&segLogRange, startBlock);
  458.     *checkPointSizePtr = 0;
  459.     full = LayoutCheckpoint(segPtr, checkPointPtr, checkPointSizePtr);
  460.  
  461.     WriteSegment(diskId, segPtr);
  462.         DestorySegStruct(segPtr);
  463.     }
  464.     return TRUE;
  465. }
  466. static Boolean
  467. WriteSegment(diskId, segPtr)
  468.     int    diskId;
  469.     LfsSeg    *segPtr;
  470. {
  471.     char    *segMemPtr;
  472.     int        len;
  473.     int        diskAddress;
  474.  
  475.     if (SegIsEmpty(segPtr)) { 
  476.     return TRUE;
  477.     }
  478.     /*
  479.      * Compute the starting disk address of this I/O.
  480.      */
  481.     diskAddress = segPtr->logRange.current * 
  482.             superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize + 
  483.           superBlockPtr->hdr.logStartOffset;
  484.     diskAddress += superBlockPtr->usageArray.segmentSize/superBlockPtr->hdr.blockSize - segPtr->curBlockOffset;
  485.  
  486.     segPtr->curElement = segPtr->numElements-1;
  487.     segPtr->curBlockOffset = 0;
  488.  
  489.     segMemPtr = alloca(superBlockPtr->usageArray.segmentSize);
  490.     CopySegToBuffer(segPtr, superBlockPtr->usageArray.segmentSize, 
  491.             segMemPtr, &len);
  492.     if (DiskWrite(diskId, diskAddress, len, segMemPtr) != len) {
  493.     fprintf(stderr, "Can't write checkpoint to disk\n");
  494.     return FALSE;
  495.     }
  496.     return TRUE;
  497. }
  498.  
  499.